﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace DataStructure.Search
{

    public class Searching
    {
        #region sequential search.
        unsafe struct SStable
        {
            // generice type
            public int* elem; // left the first space as emtpy to save key to search for determin whether link is at the end during search
            public int length;

            public static int Seq(SStable tale, int key)
            {
                int result = -1;
                return result;
            }
        }
        #endregion

        #region BinarySearch


        public int RbinSearch(List<int> list, int value, int lower, int upper)
        {
            if (lower > upper)
                return -1;
            else
            {
                int mid;
                mid = (int)(upper + lower) / 2;
                if (value < list[mid])
                    return RbinSearch(list, value, lower, mid - 1);
                else if (value == list[mid])
                    return mid;
                else
                    return RbinSearch(list, value, mid + 1, upper);
            }

        }
        public static int BinarySeach<T>(List<T> list, T key, Comparer<T> comparer)
        {
            int result = -1;
            int low = 0;
            int high = list.Count;
            while (low < high)
            {
                int min = (low + high) / 2;
                if (comparer.Compare(list[min], key) == 0)
                {
                    result = min;
                    break;
                }
                else if (comparer.Compare(list[min], key) > 0)
                {
                    high = min - 1;
                }
                else if (comparer.Compare(list[min], key) < 0)
                {
                    low = min + 1;
                }
            }
            return result;
        }

        public static int[] BinarySeachWithAll<T>(List<T> list, T key, Comparer<T> comparer)
        {
            List<int> result = new List<int>();
            int low = 0;
            int high = list.Count;
            while (low < high)
            {
                int min = (low + high) / 2;
                if (comparer.Compare(list[min], key) == 0)
                {
                    result.Add(min);
                    int tempmin = min;
                    while (--tempmin >= low)
                    {
                        if (comparer.Compare(list[tempmin], key) == 0)
                        {
                            result.Add(tempmin);
                        }
                        else
                        {
                            break;
                        }
                    }

                    tempmin = min;
                    while (++tempmin < high)
                    {
                        if (comparer.Compare(list[tempmin], key) == 0)
                        {
                            result.Add(tempmin);
                        }
                        else
                        {
                            break;
                        }
                    }
                    break;
                }
                else if (comparer.Compare(list[min], key) > 0)
                {
                    high = min - 1;
                }
                else if (comparer.Compare(list[min], key) < 0)
                {
                    low = min + 1;
                }
            }
            return result.ToArray();
        }
        #endregion

        #region BalancedBinaray tree

        #endregion

        #region red and black
        #endregion

        #region skip list
        #endregion

    }

    public class Node : IComparable
    {
        public Object element;
        public Node left;
        public Node right;
        public int height;

        public Node(Object data, Node lt, Node rt)
        {
            element = data;
            left = lt;
            right = rt;
            height = 0;
        }
        public Node(Object data)
        {
            element = data;
            left = null;
            right = null;
        }

        public int GetHeight()
        {
            if (this == null)
                return -1;
            else
                return this.height;
        }

        #region IComparable Members

        public int CompareTo(object obj)
        {
            throw new NotImplementedException();
        }

        #endregion
    }

}
